#pragma once
#ifndef _BINARYTREE_H
#define _BINARYTREE_H

#include <iostream>
#include <queue>

template <typename T> class BinaryTree;

template <typename T>
class TreeNode {

template <typename T>
friend class BinaryTree;

public:
	T val;
	TreeNode<T>* left;
	TreeNode<T>* right;
	TreeNode(const T& in):val(in) {
		left = NULL;
		right = NULL;
	}
	TreeNode() {
		left = NULL;
		right = NULL;
	}
};

template <typename T>
class BinaryTree {

public:
	TreeNode<T>* root;
	//BinaryTree(const T& in);
	//~BinaryTree();
	void visit(TreeNode<T>* cur);
	void PreOrder();
	void PreOrder(TreeNode<T>* cur);
	void InOrder();
	void InOrder(TreeNode<T>* cur);
	void PostOrder();
	void PostOrder(TreeNode<T>* cur);
	void LevelOrder();
	void LevelOrder(TreeNode<T>* cur);
	//void CreateNode(TreeNode<T>* last,bool left,bool right,const T& in);
};
/*
template <typename T>
BinaryTree<T>::BinaryTree(const T& in) {
	root = new TreeNode<T>(in);
}
*/
template <typename T>
void BinaryTree<T>::visit(TreeNode<T>* cur) {
	std::cout << cur->val;
}

template <typename T>
void BinaryTree<T>::PreOrder() {
	if (root != NULL) {
		PreOrder(root);
	}
}

template <typename T>
void BinaryTree<T>::PreOrder(TreeNode<T>* cur) {
	if (cur != NULL) {
		visit(cur);
		PreOrder(cur->left);
		PreOrder(cur->right);
	}
}

template <typename T>
void BinaryTree<T>::InOrder() {
	if (root != NULL) {
		InOrder(root);
	}
}

template <typename T>
void BinaryTree<T>::InOrder(TreeNode<T>* cur) {
	if (cur!=NULL){
		InOrder(cur->left);
		visit(cur);
		InOrder(cur->right);
	}
}

template <typename T>
void BinaryTree<T>::LevelOrder() {
	if (root != NULL) {
		LevelOrder(root);
	}
}

template <typename T>
void BinaryTree<T>::LevelOrder(TreeNode<T>* cur) {
	TreeNode<T>* tmp = cur;
	queue<TreeNode<T>*> myqueue;
	myqueue.push(cur);
	while (!myqueue.empty()){
		tmp = myqueue.front();
		visit(tmp);
		if (tmp->left != NULL) {
			myqueue.push(tmp->left);
		}
		if (tmp->right != NULL) {
			myqueue.push(tmp->right);
		}
		myqueue.pop();
	}
}

template <typename T>
void BinaryTree<T>::PostOrder() {
	if (root != NULL) {
		PostOrder(root);
	}
}

template <typename T>
void BinaryTree<T>::PostOrder(TreeNode<T>* cur) {
	if (cur != NULL) {
		PostOrder(cur->left);
		PostOrder(cur->right);
		visit(cur);
	}
}
/*
template <typename T>
void BinaryTree<T>::CreateNode(TreeNode<T>* last, bool left, bool right, const T& in) {
	if (left&&right) {
		TreeNode<T>* leftnode = new TreeNode<T>(in);
		TreeNode<T>* rightnode = new TreeNode<T>(in);
		last->left = leftnode;
		last->right = rightnode;
	}
	if (left && !right) {
		TreeNode<T>* leftnode = new TreeNode<T>(in);
		last->left = leftnode;
	}
	if (!left&&right) {
		TreeNode<T>* rightnode = new TreeNode<T>(in);
		last->right = rightnode;
	}
	if (!left && !right) {
		throw "Create null node!";
	}
}
*/
#endif